package com.xie.leetcode.array;

//318. 最大单词长度乘积
//        给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。
//        你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
//
//
//
//        示例 1:
//
//        输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
//        输出: 16
//        解释: 这两个单词为 "abcw", "xtfn"。
//        示例 2:
//
//        输入: ["a","ab","abc","d","cd","bcd","abcd"]
//        输出: 4
//        解释: 这两个单词为 "ab", "cd"。
//        示例 3:
//
//        输入: ["a","aa","aaa","aaaa"]
//        输出: 0
//        解释: 不存在这样的两个单词。
//
//
//        提示：
//
//        2 <= words.length <= 1000
//        1 <= words[i].length <= 1000
//        words[i] 仅包含小写字母

import java.util.HashMap;
import java.util.Map;

/**
 * @author xiezhendong
 * @date 2021/11/17
 */
public class MaxProduct {

    public static void main(String[] args) {
        MaxProduct maxProduct = new MaxProduct();
        System.out.println(maxProduct.maxProduct(new String[]{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}));
        System.out.println(maxProduct.maxProduct(new String[]{"a", "ab", "abc", "d", "cd", "bcd", "abcd"}));
        System.out.println(maxProduct.maxProduct(new String[]{"a", "aa", "aaa", "aaaa"}));
    }

    public int maxProduct(String[] words) {
        int value = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int h = 0;
            for (int j = 0; j < word.length(); j++) {
                h |= 1 << (word.charAt(j) - 'a');
            }
            int n = word.length();
            if (map.containsKey(h) && map.get(h) >= n) {
                continue;
            }
            for (int other : map.keySet()) {
                if ((other & h) == 0) {
                    value = Math.max(value, map.get(other) * n);
                }
            }
            map.put(h, n);
        }
        return value;
    }
}
